#include <stdio.h>
#include <stdlib.h>

int dynamic_1(int n, int v, int *c, int *w)
{
    int i, j;

    if (v == 0)
        return 0;
    
    if (n == 1)
    {
        if (c[0] <= v)
            return w[0];
        else
            return 0;
    }

    i = j = 0;
    if (c[n-1] <= v)
        i = dynamic_1(n-1, v-c[n-1], c, w) + w[n-1];
    j = dynamic_1(n-1, v, c, w);

    return i>j?i:j;
}

int dynamic_2(int n, int v, int *c, int *w)
{
    int i, j, ret, *t;

    t = calloc(v, sizeof(int));

    for (i = 0; i < n; i++) {
        for (j = v; j >= c[i]; j--) {
            if (j == c[i] && t[j-1] < w[i])
                t[j-1] = w[i];
            else if (t[j-1] < t[j-c[i]-1] + w[i])
                t[j-1] = t[j-c[i]-1] + w[i];
        }
    }

    ret = t[v-1];

    free(t);
    return ret;
}

int main(int argc, char const* argv[])
{
    int n = 5;
    int v = 23;
    int c[] = {5, 6, 8, 11, 12};
    int w[] = {19, 24, 33, 45, 50};

    printf("totalw is %d\n", dynamic_1(n, v, c, w));
    printf("totalw is %d\n", dynamic_2(n, v, c, w));
    return 0;
}
